package class03;

import java.util.Arrays;

/**
 * @description: 二分法解决局部最小值问题
 *                数组arr无序，但任何相邻的两个数不等，定义局部最小值的概念：
 *                  若 arr[0] < arr[1],return arr[0];
 *                  若 arr[N-1] < arr[N-2],return arr[N-1];
 *                  若 arr[i-1] > arr[i] < arr[i+1],return arr[i];
 *                只需要返回一个即可，若数组 arr 无局部最小，return -1;
 * @time: 2021/7/7 13:35
 * @author: lhy
 */
public class BSLocalMinimum {

    /**
     * 二分搜索寻找局部最小值
     * @param arr 无序、相邻值不等数组
     * @return index
     */
    public static int binarySearchLocalMin(int[] arr){
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int length = arr.length;
        if (length == 1) {
            return 0;
        }
        if (arr[0] < arr[1]) {
            return 0;
        }
        if (arr[length - 1] < arr[length - 2]) {
            return length - 1;
        }
        int l = 0;
        int r = length - 1;
        // l...r 肯定有局部最小
        while (l < r - 1) {
            int mid = l + (r - l) / 2;
            if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                return mid;
            } else {
                if (arr[mid] > arr[mid - 1]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return arr[l] < arr[r] ? l : r;
    }

    /**
     *  检测函数，binarySearchLocalMin() 函数返回的是否为局部最小
     * @param arr 待检测数组
     * @param index binarySearchLocalMin返回的索引
     * @return true/false
     */
    public static boolean test(int[] arr,int index){
        if (index == -1){
            return false;
        }
        int len = arr.length;
        if (arr[index] == arr[0] || arr[index] == arr[len-1]){
            return true;
        }
        return arr[index] < arr[index - 1] && arr[index] < arr[index + 1];
    }

    /**
     * 生成任何相邻值不等的随机数组
     * @param maxLen 数组的最大长度
     * @param maxValue 数组的最大值
     * @return arr
     */
    public static int[] generateAdjacentUnequalRandomArray(int maxLen, int maxValue){
        int len = (int) (Math.random() * maxLen) + 1;
        int[] arr = new int[len];
        int cur = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
        arr[0] = cur;
        for (int i = 1; i < len; i++) {
            do {
                cur = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
            }while (cur == arr[i-1]);
            arr[i] = cur;
        }
        return arr;
    }


    public static void main(String[] args) {
        int testTimes = 10000;
        int maxLen = 100;
        int maxValue = 1000;
        System.out.println(">>>Test start...");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateAdjacentUnequalRandomArray(maxLen,maxValue);
            int index = binarySearchLocalMin(arr);
            if (index == -1){
                System.out.println("No LocalMin.");
                System.out.println("Array: " + Arrays.toString(arr));
                break;
            }
            boolean succeed = test(arr,index);
            if (!succeed) {
                System.out.println("Error!");
                System.out.println("Array: " + Arrays.toString(arr));
                System.out.println("index: " + index);
                break;
            }
        }
        System.out.println(">>>Test end.");
    }
}
